/// @tags: ConstantCoefficientLinearHomogeneousRecurrence PolyMod PolyDiv
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

namespace BlueQuantum {

typedef long long LL;

int const N = 1 << 18, P = 998244353, g = 3, ig = 332748118;

class Polynomial {
 private:
  int n;
  int f[N];
  static int Cvt[N << 2];

 public:
  void NTT(bool const typ, int const n);
  void inv(Polynomial &Res, int const n) const;
  void mod(Polynomial &R, Polynomial const &D, int const n, int const m) const;
  Polynomial operator*(Polynomial const &rhs) const;
  inline int *operator&() { return f; }
  inline int &operator[](int index) { return f[index]; };
  inline int const &operator[](int index) const { return f[index]; };
  inline static void prework(int n) {
    for (int len = 2; len <= n; len <<= 1)
      for (int j = 1, *const cvt = Cvt + len - 1; j < len; ++j)
        cvt[j] = cvt[j >> 1] >> 1 | (j & 1) * (len >> 1);
  }
  inline void clear(int n) {
    int maxl = 1;
    while (maxl < n) maxl <<= 1;
    memset(f, 0, sizeof(int) * maxl);
  }
} A, Base, Mod, Res, Tmp;

int Polynomial::Cvt[N << 2];

inline LL qpow(LL base, int exp) {
  LL Res = 1;
  while (exp) {
    if (exp & 1) Res = Res * base % P;
    base = base * base % P;
    exp >>= 1;
  }
  return Res;
}

/// @param typ 正/逆向 @param n 项数 必须是2的整数次幂
inline void Polynomial::NTT(bool const typ, int const n) {
  for (int i = 1, *const cvt = Cvt + n - 1; i < n; ++i)
    if (i < cvt[i]) std::swap(f[i], f[cvt[i]]);
  for (int i = 2; i <= n; i <<= 1) {
    int mid = i >> 1, wn = qpow(typ ? g : ig, (P - 1) / i);
    for (int j = 0; j < n; j += i) {
      LL wk = 1;
      for (int k = 0; k < mid; ++k, (wk *= wn) %= P) {
        LL t = wk * f[j + k + mid] % P;
        if ((f[j + k + mid] = f[j + k] - t) < 0) f[j + k + mid] += P;
        if ((f[j + k] += t) >= P) f[j + k] -= P;
      }
    }
  }
  if (!typ) {
    LL inv = qpow(n, P - 2);
    for (int i = 0; i < n; ++i) f[i] = inv * f[i] % P;
  }
}

/// @param Res 应清空 @param n 模的次数（项数）
inline void Polynomial::inv(Polynomial &Res, int const n) const {
  static Polynomial Tmp;
  if (n == 1) return Res[0] = qpow(f[0], P - 2), void();
  inv(Res, (n + 1) >> 1);
  int maxl = 1;
  while (maxl < n << 1) maxl <<= 1;  // n - 1 次多项式卷 ⌈n / 2⌉ - 1 次多项式
  Tmp.clear(n << 1);
  memcpy(&Tmp, f, sizeof(int) * n);
  Tmp.NTT(true, maxl), Res.NTT(true, maxl);
  for (int i = 0; i < maxl; ++i)
    Res[i] = static_cast<LL>(Res[i]) *
             ((2ll - static_cast<LL>(Res[i]) * Tmp[i] % P + P) % P) % P;
  Res.NTT(false, maxl);
  for (int i = n; i < maxl; ++i) Res[i] = 0;  // mod x^n
}

/// @param R Remainder (m-1)D @param D Divider @param n Self Degree @param m Divider
/// Degree
inline void Polynomial::mod(Polynomial &R, Polynomial const &D, int const n,
                            int const m) const {
  if (n < m) return void(memcpy(&R, f, (m - 1) * sizeof(int)));
  static Polynomial Dr, iDr, Fr, Q;
  int maxl = 1;
  while (maxl < n * 2 - m + 1) maxl <<= 1;
  memset(&Dr, 0, sizeof(int) * maxl);
  memset(&iDr, 0, sizeof(int) * maxl);
  memset(&Fr, 0, sizeof(int) * maxl);
  for (int i = 0; i <= m; ++i) Dr[i] = D[m - i];
  for (int i = 0; i <= n; ++i) Fr[i] = f[n - i];
  Dr.inv(iDr, n - m + 1);
  iDr.NTT(true, maxl), Fr.NTT(true, maxl);
  for (int i = 0; i < maxl; ++i) Q[i] = (LL)iDr[i] * Fr[i] % P;
  Q.NTT(false, maxl);
  for (int i = n - m + 1; i < maxl; ++i) Q[i] = 0;
  std::reverse(&Q, &Q + n - m + 1);
  std::reverse(&Dr, &Dr + m + 1);
  Q.NTT(true, maxl), Dr.NTT(true, maxl);
  for (int i = 0; i < maxl; ++i) R[i] = (LL)Q[i] * Dr[i] % P;
  R.NTT(false, maxl);
  for (int i = 0; i < m; ++i)
    if ((R[i] = f[i] - R[i]) < 0) R[i] += P;
  for (int i = m; i < maxl; ++i) R[i] = 0;
}

int n, k;

inline int main() {
  cin >> n >> k;
  for (int i = k - 1; i >= 0; --i) cin >> Mod[i], Mod[i] = Mod[i] ? (P - Mod[i]) % P : 0;
  for (int i = 0; i < k; ++i) cin >> A[i], A[i] += A[i] < 0 ? P : 0;
  Mod[k] = 1, Base[1] = 1, Res[0] = 1;
  int exp = n, maxl = 1;
  while (maxl < k << 1) maxl <<= 1;
  Polynomial::prework(maxl << 2);
  while (exp) {
    if (exp & 1) {
      Res.NTT(true, maxl), Base.NTT(true, maxl);
      for (int i = 0; i < maxl; ++i) Res[i] = (LL)Res[i] * Base[i] % P;
      Res.NTT(false, maxl), Base.NTT(false, maxl);
      int mi = k << 1;
      while (!Res[mi]) mi--;
      Res.mod(Tmp, Mod, mi, k);
      memcpy(&Res, &Tmp, sizeof(int) * maxl);
      memset(&Tmp, 0, sizeof(int) * maxl);
    }
    Base.NTT(true, maxl);
    for (int i = 0; i < maxl; ++i) Base[i] = (LL)Base[i] * Base[i] % P;
    Base.NTT(false, maxl);
    int mi = k << 1;
    while (!Base[mi]) mi--;
    Base.mod(Tmp, Mod, mi, k);
    memcpy(&Base, &Tmp, sizeof(int) * maxl);
    memset(&Tmp, 0, sizeof(int) * maxl);
    exp >>= 1;
  }
  LL ans = 0;
  for (int i = 0; i < k; ++i)
    if ((ans += (LL)A[i] * Res[i] % P) >= P) ans -= P;
  cout << ans;
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("ConstCoLinearRecurrence.in", "r", stdin);
  freopen("ConstCoLinearRecurrence.out", "w", stdout);
#endif
#endif

  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
